0982. 按位与为零的三元组【困难】

• 1. 📝 题目描述
• 2. 🎯 s.1 - 哈希表优化

1. 📝 题目描述

• leetcode

给你一个整数数组 nums，返回其中 按位与三元组 的数目。

按位与三元组 是由下标 (i, j, k) 组成的三元组，并满足下述全部条件：

• 0 <= i < nums.length
• 0 <= j < nums.length
• 0 <= k < nums.length
• nums[i] & nums[j] & nums[k] == 0，其中 & 表示按位与运算符。

---

示例 1：

输入：nums = [2,1,3]
输出：12

解释：
可以选出如下 i, j, k 三元组：
(i=0, j=0, k=1) : 2 & 2 & 1
(i=0, j=1, k=0) : 2 & 1 & 2
(i=0, j=1, k=1) : 2 & 1 & 1
(i=0, j=1, k=2) : 2 & 1 & 3
(i=0, j=2, k=1) : 2 & 3 & 1
(i=1, j=0, k=0) : 1 & 2 & 2
(i=1, j=0, k=1) : 1 & 2 & 1
(i=1, j=0, k=2) : 1 & 2 & 3
(i=1, j=1, k=0) : 1 & 1 & 2
(i=1, j=2, k=0) : 1 & 3 & 2
(i=2, j=0, k=1) : 3 & 2 & 1
(i=2, j=1, k=0) : 3 & 1 & 2

---

示例 2：

输入：nums = [0,0,0]
输出：27

---

提示：

• 1 <= nums.length <= 1000
• 0 <= nums[i] < 2^16

2. 🎯 s.1 - 哈希表优化

js

/**
 * @param {number[]} nums
 * @return {number}
 */
var countTriplets = function (nums) {
  const n = nums.length
  const map = new Map() // 记录所有两两按位与的结果及其出现次数

  // 预处理：计算所有 nums[i] & nums[j] 的结果
  for (let i = 0; i < n; i++) {
    for (let j = 0; j < n; j++) {
      const and = nums[i] & nums[j]
      map.set(and, (map.get(and) || 0) + 1)
    }
  }

  let count = 0
  // 遍历所有两两按位与的结果和第三个元素
  for (const [and, freq] of map) {
    for (let k = 0; k < n; k++) {
      // 如果三者按位与为 0，累加计数
      if ((and & nums[k]) === 0) {
        count += freq
      }
    }
  }

  return count
}

• 时间复杂度：$O(n^2+n\times m)$，其中 n 是数组长度，m 是不同的两两按位与结果数量（最多 $2^{16}$），预处理 $O(n^2)$，统计 $O(n\times m)$
• 空间复杂度：$O(m)$，哈希表存储所有不同的两两按位与结果

算法思路：

• 预处理阶段：计算所有 nums[i] & nums[j] 的结果，用哈希表记录每种结果的出现次数
• 统计阶段：遍历哈希表中的所有两两按位与结果和数组中的第三个元素 nums[k]
• 按位与判断：如果 (nums[i] & nums[j]) & nums[k] == 0，说明找到一个有效三元组
• 计数累加：将该两两按位与结果的出现次数累加到总计数中
• 优化原理：将三层循环优化为两层，通过哈希表避免重复计算两两按位与的结果